﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
// 原题连接：https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/
/*
题目描述：
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
*/

// 开始解题：
// 方法1——快慢指针
struct ListNode* deleteMiddle(struct ListNode* head) {
    if (NULL == head || NULL == head->next) {
        return NULL;
    }
    // 先找到链表的中间节点
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* pre = NULL;
    while (fast && fast->next) {
        fast = fast->next->next;
        pre = slow;
        slow = slow->next;
    }
    pre->next = pre->next->next;
    return head;

}
// 时间复杂度：O(n)，n为链表的长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。